{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Number of Non-Overlapping Subarrays With Sum Equals Target"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #hash-table #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #哈希表 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxNonOverlapping"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #和为目标值且不重叠的非空子数组的最大数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个数组&nbsp;<code>nums</code>&nbsp;和一个整数&nbsp;<code>target</code>&nbsp;。</p>\n",
    "\n",
    "<p>请你返回&nbsp;<strong>非空不重叠</strong>&nbsp;子数组的最大数目，且每个子数组中数字和都为 <code>target</code>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [1,1,1,1,1], target = 2\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>总共有 2 个不重叠子数组（加粗数字表示） [<strong>1,1</strong>,1,<strong>1,1</strong>] ，它们的和为目标值 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [-1,3,5,1,4,2,-9], target = 6\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>总共有 3 个子数组和为 6 。\n",
    "([5,1], [4,2], [3,5,1,4,2,-9]) 但只有前 2 个是不重叠的。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [-2,6,6,3,5,4,1,2,8], target = 10\n",
    "<strong>输出：</strong>3\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [0,0,0], target = 0\n",
    "<strong>输出：</strong>3\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;=&nbsp;10^5</code></li>\n",
    "\t<li><code>-10^4 &lt;= nums[i] &lt;=&nbsp;10^4</code></li>\n",
    "\t<li><code>0 &lt;= target &lt;= 10^6</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-number-of-non-overlapping-subarrays-with-sum-equals-target](https://leetcode.cn/problems/maximum-number-of-non-overlapping-subarrays-with-sum-equals-target/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-number-of-non-overlapping-subarrays-with-sum-equals-target](https://leetcode.cn/problems/maximum-number-of-non-overlapping-subarrays-with-sum-equals-target/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,1,1,1,1]\\n2', '[-1,3,5,1,4,2,-9]\\n6']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonOverlapping(self, nums: List[int], target: int) -> int:\n",
    "        s = {0}\n",
    "        cur_sum = 0\n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            cur_sum += num\n",
    "            if cur_sum - target in s:\n",
    "                s = {0}\n",
    "                cur_sum = 0\n",
    "                ans += 1\n",
    "            else:\n",
    "                s.add(cur_sum)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonOverlapping(self, nums: List[int], target: int) -> int:\n",
    "\n",
    "        sum_ = 0\n",
    "        mp = set([0])\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        for i, n in enumerate(nums):\n",
    "            sum_ += n\n",
    "            if sum_ - target in mp:\n",
    "                ans += 1\n",
    "                sum_ = 0\n",
    "                mp = set([0])\n",
    "            else:\n",
    "                mp.add(sum_)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonOverlapping(self, nums: List[int], target: int) -> int:\n",
    "        pre_set = {0, }\n",
    "        pre = 0\n",
    "        ans = 0\n",
    "        for x in nums:\n",
    "            pre += x\n",
    "            if pre - target in pre_set:\n",
    "                ans += 1\n",
    "                pre_set = {pre, }\n",
    "            else:\n",
    "                pre_set.add(pre)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonOverlapping(self, nums: List[int], target: int) -> int:\n",
    "        pre_set = {0, }\n",
    "        pre = 0\n",
    "        ans = 0\n",
    "        for x in nums:\n",
    "            pre += x\n",
    "            if pre - target in pre_set:\n",
    "                ans += 1\n",
    "                pre_set = {pre, }\n",
    "            else:\n",
    "                pre_set.add(pre)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonOverlapping(self, nums: List[int], target: int) -> int:\n",
    "        size = len(nums)\n",
    "        ret = 0\n",
    "        i = 0\n",
    "        while i < size:\n",
    "            s = {0}\n",
    "            total = 0\n",
    "            while i < size:\n",
    "                total += nums[i]\n",
    "                if total - target in s:\n",
    "                    ret += 1\n",
    "                    break\n",
    "                else:\n",
    "                    s.add(total)\n",
    "                    i += 1\n",
    "            i += 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonOverlapping(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        ret = 0\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            s = {0}\n",
    "            total = 0\n",
    "            while i < n:\n",
    "                total += nums[i]\n",
    "                if total - target in s:\n",
    "                    ret += 1\n",
    "                    break\n",
    "                else:\n",
    "                    s.add(total)\n",
    "                    i += 1\n",
    "            i += 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonOverlapping(self, nums: List[int], target: int) -> int:\n",
    "        ans = 0\n",
    "        i, n = 0, len(nums)\n",
    "        while i < n:\n",
    "            his = {0}\n",
    "            total = 0\n",
    "            while i < n:\n",
    "                total += nums[i]\n",
    "                if total - target in his:\n",
    "                    ans += 1\n",
    "                    break\n",
    "                else:\n",
    "                    his.add(total)\n",
    "                    i += 1\n",
    "            i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonOverlapping(self, nums: List[int], target: int) -> int:\n",
    "        \n",
    "        s={0}\n",
    "        sum=0\n",
    "        ans=0\n",
    "        for num in nums:\n",
    "            sum+=num\n",
    "            if sum - target in s:\n",
    "                s={0}\n",
    "                sum=0    \n",
    "                ans+=1\n",
    "            else:\n",
    "                s.add(sum)\n",
    "        return ans\n",
    "                \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonOverlapping(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        i = 0\n",
    "        res = 0\n",
    "        while i < n:\n",
    "            hash_set = {0}\n",
    "            prix = 0\n",
    "            while i < n:\n",
    "                prix += nums[i]\n",
    "                i += 1\n",
    "                if prix - target in hash_set:\n",
    "                    res += 1\n",
    "                    break\n",
    "                else:\n",
    "                    hash_set.add(prix)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonOverlapping(self, nums: List[int], target: int) -> int:\n",
    "        length = len(nums)\n",
    "        res = 0\n",
    "        i = 0\n",
    "        while i<length:\n",
    "            total = 0\n",
    "            pre = {0}\n",
    "            while i<length:\n",
    "                total += nums[i]\n",
    "                if total-target in pre:\n",
    "                    res += 1\n",
    "                    break\n",
    "                else:\n",
    "                    pre.add(total)\n",
    "                    i += 1\n",
    "            i += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonOverlapping(self, nums: List[int], target: int) -> int:\n",
    "        res = 0\n",
    "        he_set = {0}\n",
    "        s = 0\n",
    "        for num in nums:\n",
    "            s += num\n",
    "            if s - target in he_set:\n",
    "                res += 1\n",
    "                he_set = {0}\n",
    "                s = 0\n",
    "            else:\n",
    "                he_set.add(s)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonOverlapping(self, nums: List[int], target: int) -> int:\n",
    "        size = len(nums)\n",
    "        ret = 0\n",
    "        i = 0\n",
    "        while i < size:\n",
    "            s = {0}\n",
    "            total = 0\n",
    "            while i < size:\n",
    "                total += nums[i]\n",
    "                if total - target in s:\n",
    "                    ret += 1\n",
    "                    break\n",
    "                else:\n",
    "                    s.add(total)\n",
    "                    i += 1\n",
    "            i += 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonOverlapping(self, nums: List[int], target: int) -> int:\n",
    "        s = {0}\n",
    "        cur_sum = 0\n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            cur_sum += num\n",
    "            if cur_sum - target in s:\n",
    "                s = {0}\n",
    "                cur_sum = 0\n",
    "                ans += 1\n",
    "            else:\n",
    "                s.add(cur_sum)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonOverlapping(self, nums: List[int], target: int) -> int:\n",
    "        s = {0}\n",
    "        cur_sum = 0\n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            cur_sum += num\n",
    "            if cur_sum - target in s:\n",
    "                s = {0}\n",
    "                cur_sum = 0\n",
    "                ans += 1\n",
    "            else:\n",
    "                s.add(cur_sum)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonOverlapping(self, nums: List[int], target: int) -> int:\n",
    "        s = {0}\n",
    "        cur_sum = 0\n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            cur_sum += num\n",
    "            if cur_sum - target in s:\n",
    "                s = {0}\n",
    "                cur_sum = 0\n",
    "                ans += 1\n",
    "            else:\n",
    "                s.add(cur_sum)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonOverlapping(self, nums: List[int], target: int) -> int:\n",
    "        ans = x= 0\n",
    "        pre = {0}\n",
    "        for num in nums:\n",
    "            x += num\n",
    "            if x - target in pre:\n",
    "                ans += 1\n",
    "                pre = {0}\n",
    "                x = 0\n",
    "            else:\n",
    "                pre.add(x)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonOverlapping(self, nums: List[int], target: int) -> int:\n",
    "        list_sum = {0}\n",
    "        count = 0\n",
    "        sub_sum = 0\n",
    "        for i in nums:\n",
    "            sub_sum += i\n",
    "            if sub_sum - target in list_sum:\n",
    "                list_sum = {0}\n",
    "                count += 1\n",
    "                sub_sum = 0\n",
    "            else:\n",
    "                list_sum.add(sub_sum)\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonOverlapping(self, nums: List[int], target: int) -> int:\n",
    "        \n",
    "        s={0}\n",
    "        sum=0\n",
    "        ans=0\n",
    "        for num in nums:\n",
    "            sum+=num\n",
    "            if sum - target in s:\n",
    "                s={0}\n",
    "                sum=0    \n",
    "                ans+=1\n",
    "            else:\n",
    "                s.add(sum)\n",
    "        return ans\n",
    "                \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonOverlapping(self, nums: List[int], target: int) -> int:\n",
    "        size = len(nums)\n",
    "        ret = 0\n",
    "        i = 0\n",
    "        while i < size:\n",
    "            s = {0}\n",
    "            total = 0\n",
    "            while i < size:\n",
    "                total += nums[i]\n",
    "                if total - target in s:\n",
    "                    ret += 1\n",
    "                    break\n",
    "                else:\n",
    "                    s.add(total)\n",
    "                    i += 1\n",
    "            i += 1\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonOverlapping(self, nums: List[int], target: int) -> int:\n",
    "        ans = 0\n",
    "        cnt = dict()\n",
    "        cnt[0] = 1\n",
    "        sm = 0\n",
    "        for x in nums:\n",
    "            sm += x\n",
    "            if sm - target in cnt:\n",
    "                ans += 1\n",
    "                cnt = dict()\n",
    "                cnt[0] = 1\n",
    "                sm = 0\n",
    "            else:\n",
    "                cnt[sm] = 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonOverlapping(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        sums = [0]\n",
    "        for i in range(1, n + 1):\n",
    "            sums.append(sums[i-1] + nums[i-1])\n",
    "        i = 0\n",
    "        ret = 0\n",
    "        set_ = set()\n",
    "        while i <= n:\n",
    "            if sums[i]- target in set_:\n",
    "                ret += 1\n",
    "                set_.clear()\n",
    "                continue\n",
    "            else:\n",
    "                set_.add(sums[i])\n",
    "            i +=1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonOverlapping(self, nums: List[int], target: int) -> int:\n",
    "        #如果可以是负的就不能这么做了、、\n",
    "        #一旦完成了一个数组则b_index立刻更新到当前的位置\n",
    "        nums=[0]+nums\n",
    "        n=len(nums)\n",
    "        for i in range(1,n):\n",
    "            nums[i]+=nums[i-1]\n",
    "        b_index=0\n",
    "        #print(nums)\n",
    "        res=0\n",
    "        visited=set()\n",
    "        for i in range(n):\n",
    "            #print(b_index,visited)\n",
    "            # while b_index+1!=i and nums[i]-nums[b_index]>target: #太大了没用 \n",
    "            #     b_index+=1\n",
    "            #太大了可能碰到负数也有用\n",
    "            if nums[i]-target in visited: #寻找有没有nums[i]-target\n",
    "                res+=1\n",
    "                b_index=i #b_index立刻更新到当前位置,中间的数字都不需要了\n",
    "                visited=set()\n",
    "            visited.add(nums[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonOverlapping(self, nums: List[int], target: int) -> int:\n",
    "        visited = {}\n",
    "        res = 0\n",
    "        for i in range(1, len(nums)):\n",
    "            nums[i] += nums[i-1]\n",
    "\n",
    "        nums.insert(0, 0)\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]-target in visited:\n",
    "                res += 1\n",
    "                visited = {}\n",
    "            visited[nums[i]] = 1\n",
    "        return res\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonOverlapping(self, nums: List[int], target: int) -> int:\n",
    "        visited = {}\n",
    "        res = 0\n",
    "        for i in range(1, len(nums)):\n",
    "            nums[i] += nums[i-1]\n",
    "\n",
    "        nums.insert(0, 0)\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]-target in visited:\n",
    "                res += 1\n",
    "                visited = {}\n",
    "            visited[nums[i]] = 1\n",
    "        return res\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonOverlapping(self, nums: List[int], target: int) -> int:\n",
    "        acc = list(accumulate(nums,initial = 0))\n",
    "        d = {}\n",
    "        ans = 0\n",
    "        for i,v in enumerate(acc):\n",
    "            if v - target in d:\n",
    "                ans += 1\n",
    "                d = {}\n",
    "            d[v] = 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonOverlapping(self, nums: List[int], target: int) -> int:\n",
    "        acc = list(accumulate(nums, initial=0))\n",
    "        cnt = 0\n",
    "        d = {}\n",
    "        for i,suf in enumerate(acc):\n",
    "            if suf-target in d:\n",
    "                cnt += 1\n",
    "                d = {}\n",
    "            d[suf] = 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonOverlapping(self, nums: List[int], target: int) -> int:\n",
    "        pre = [0]\n",
    "        d = {}\n",
    "        res = 0\n",
    "        for num in nums:\n",
    "            pre.append(pre[-1] + num)\n",
    "        for i, num in enumerate(pre):\n",
    "            if num in d:\n",
    "                res += 1\n",
    "                d = {}\n",
    "            d[target + num] = i\n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonOverlapping(self, nums: List[int], target: int) -> int:\n",
    "        acc = list(accumulate(nums, initial=0))\n",
    "        cnt = 0\n",
    "        d = {}\n",
    "        for i,num in enumerate(acc):\n",
    "            if num in d:\n",
    "                cnt += 1\n",
    "                d = {}\n",
    "            d[target + num] = i\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonOverlapping(self, nums: List[int], target: int) -> int:\n",
    "        acc = list(accumulate(nums, initial=0))\n",
    "        cnt = 0\n",
    "        d = {}\n",
    "        for i,num in enumerate(acc):\n",
    "            if num in d:\n",
    "                cnt += 1\n",
    "                d = {}\n",
    "            d[target + num] = i\n",
    "        return cnt\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonOverlapping(self, nums: List[int], target: int) -> int:\n",
    "        n=len(nums)\n",
    "        dic={}\n",
    "        dic[0]=-1\n",
    "        tsum=0\n",
    "        res=0\n",
    "        ed=-1\n",
    "        for i in range(n):\n",
    "            tsum+=nums[i]\n",
    "            if tsum-target in dic.keys():\n",
    "                if dic[tsum-target]+1>ed:\n",
    "                    res+=1\n",
    "                    ed=i\n",
    "            dic[tsum]=i \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def maxNonOverlapping(self, nums: List[int], target: int) -> int:\n",
    "    l = len(nums)\n",
    "    r = {}\n",
    "    r[0] = 0\n",
    "    c = [0] * l\n",
    "    s = 0\n",
    "    for i in range(l):\n",
    "      v = nums[i]\n",
    "      s += v\n",
    "      f = s - target\n",
    "      if f in r:\n",
    "        # print(f\"find pair {i} -> {r[f]}\")\n",
    "        c[i] = max(c[i - 1], c[r[f] - 1] + 1)\n",
    "      elif v == target:\n",
    "        c[i] = c[i - 1] + 1\n",
    "      else:\n",
    "        c[i] = c[i - 1]\n",
    "      r[s] = i + 1\n",
    "    # print(f\"r {r}\")\n",
    "    # print(f\"a {nums}\")\n",
    "    # print(f\"c {c}\")\n",
    "    return c[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonOverlapping(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        prev = -1\n",
    "        mp = {0 : -1}\n",
    "        curs = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            curs += nums[i]\n",
    "            if curs - target in mp:\n",
    "                if mp[curs - target] >= prev:\n",
    "                    prev = i\n",
    "                    ans += 1\n",
    "            mp[curs] = i\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonOverlapping(self, nums: List[int], target: int) -> int:\n",
    "        ans = 0\n",
    "\n",
    "        count = {0: -1}\n",
    "        now = -1\n",
    "        last = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            last += num\n",
    "            if last - target in count and count[last - target] >= now:\n",
    "                now = i\n",
    "                ans += 1\n",
    "            count[last] = i\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonOverlapping(self, nums: List[int], target: int) -> int:\n",
    "        # 用哈希表记录前缀和的下标，那么要找区间和为target的子数组，就是找到\n",
    "        # 和为 pre - target 的前缀和的下标索引。且 这个pre-target的下标需要超过之前的\n",
    "        # 右端点，因为不能重叠\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        rec = dict()\n",
    "        rec[0] = -1\n",
    "        pre,end = 0, -1\n",
    "        for i in range(n):\n",
    "            pre += nums[i]\n",
    "            if pre - target in rec:\n",
    "                if rec[pre-target]>=end:\n",
    "                    res+=1\n",
    "                    end = i\n",
    "            rec[pre] = i\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonOverlapping(self, nums: List[int], target: int) -> int:\n",
    "        result = 0\n",
    "        index_mappping = defaultdict(int)\n",
    "        index_mappping[0] = -1\n",
    "        max_ind = float(\"-inf\")\n",
    "        total = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            total += num\n",
    "            tmp = total - target\n",
    "            # if num == 2:\n",
    "            #     print(total, index_mappping)\n",
    "            if tmp in index_mappping and max_ind <= index_mappping[tmp]:\n",
    "                # print(i, index_mappping[tmp])\n",
    "                result += 1\n",
    "                max_ind = i\n",
    "            index_mappping[total] = i\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonOverlapping(self, nums: List[int], t: int) -> int:\n",
    "        n = len(nums)\n",
    "        mp = {0 :-1}\n",
    "        prev = -1\n",
    "        ans = 0\n",
    "        curs = 0\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            curs += num\n",
    "            # 表示[prev + 1, i]区间出现了目标值\n",
    "            if curs - t in mp:\n",
    "                # 保证开始在结束之后，prev是结束点\n",
    "                if mp[curs - t] >= prev:\n",
    "                    ans += 1\n",
    "                    prev = i\n",
    "            mp[curs] = i\n",
    "        \n",
    "        return ans\n",
    "                    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonOverlapping(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        rec = dict()\n",
    "        rec[0] = -1\n",
    "        pre,end = 0, -1\n",
    "        for i in range(n):\n",
    "            pre += nums[i]\n",
    "            if pre - target in rec:\n",
    "                if rec[pre-target]>=end:\n",
    "                    res+=1\n",
    "                    end = i\n",
    "            rec[pre] = i\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonOverlapping(self, nums: List[int], target: int) -> int:\n",
    "                    last = Counter()\n",
    "                    s = 0\n",
    "                    f = [0] * (len(nums) + 1)\n",
    "                    for i,x in enumerate(nums,1):\n",
    "                        s += x\n",
    "                        if last[s - target]:\n",
    "                            f[i] = f[last[s - target]] + 1\n",
    "                        if s == target:\n",
    "                            f[i] = max(f[i],1)\n",
    "                        last[s] = i\n",
    "                        f[i] = max(f[i-1],f[i])\n",
    "                    #     print(s,last)\n",
    "                    # print(f)\n",
    "                    return max(f)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonOverlapping(self, nums: List[int], target: int) -> int:\n",
    "        d = collections.defaultdict(int)\n",
    "        d[0] = -1\n",
    "        s = e = -1\n",
    "        ss = ret = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            ss += num\n",
    "            if (ss - target) in d:\n",
    "                s = d[ss - target] + 1\n",
    "                if s > e:\n",
    "                    e = i\n",
    "                    ret += 1\n",
    "            d[ss] = i\n",
    "        return ret\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def maxNonOverlapping(self, nums: List[int], target: int) -> int:\n",
    "    l = len(nums)\n",
    "    r = {}\n",
    "    r[0] = 0\n",
    "    c = [0] * l\n",
    "    s = 0\n",
    "    ret = 0\n",
    "    for i in range(l):\n",
    "      v = nums[i]\n",
    "      s += v\n",
    "      \n",
    "      f = s - target\n",
    "      if f in r:\n",
    "        # print(f\"find pair {i} -> {r[f]}\")\n",
    "        c[i] = max(c[i - 1], c[r[f] - 1] + 1)\n",
    "      elif v == target:\n",
    "        c[i] = c[i - 1] + 1\n",
    "      else:\n",
    "        c[i] = c[i - 1]\n",
    "      r[s] = i + 1\n",
    "      ret = max(ret, c[i])\n",
    "    # print(f\"r {r}\")\n",
    "    # print(f\"a {nums}\")\n",
    "    # print(f\"c {c}\")\n",
    "    return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def maxNonOverlapping(self, nums: List[int], target: int) -> int:\n",
    "    l = len(nums)\n",
    "    r = {}\n",
    "    r[0] = 0\n",
    "    c = [0] * l\n",
    "    s = 0\n",
    "    for i in range(l):\n",
    "      v = nums[i]\n",
    "      s += v\n",
    "      f = s - target\n",
    "      if f in r:\n",
    "        # print(f\"find pair {i} -> {r[f]}\")\n",
    "        c[i] = max(c[i - 1], c[r[f] - 1] + 1)\n",
    "      elif v == target:\n",
    "        c[i] = c[i - 1] + 1\n",
    "      else:\n",
    "        c[i] = c[i - 1]\n",
    "      r[s] = i + 1\n",
    "    # print(f\"r {r}\")\n",
    "    # print(f\"a {nums}\")\n",
    "    # print(f\"c {c}\")\n",
    "    return c[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonOverlapping(self, nums: List[int], target: int) -> int:\n",
    "        ls = []\n",
    "\n",
    "        sum_ = 0\n",
    "\n",
    "        mp = collections.defaultdict(int)\n",
    "        mp[0] = -1\n",
    "        for i, n in enumerate(nums):\n",
    "            sum_ += n \n",
    "            rem = sum_ - target\n",
    "\n",
    "            if rem in mp:\n",
    "                # ls.extend([[start + 1, i]for start in mp[rem]])\n",
    "                ls.append([mp[rem] + 1, i])\n",
    "            mp[sum_] = i\n",
    "\n",
    "        if len(ls) <= 1:\n",
    "            return len(ls)\n",
    "\n",
    "        \n",
    "        ls.sort(key = lambda x:x[1])\n",
    "\n",
    "        dp = [1] * len(ls)\n",
    "        \n",
    "        max_ = 1\n",
    "\n",
    "        for i in range(1, len(dp)):\n",
    "            st, ed = ls[i]\n",
    "\n",
    "            # check ed < st 的最大值\n",
    "\n",
    "            left = -1\n",
    "            right = i - 1\n",
    "\n",
    "            while left < right:\n",
    "                mid = left + (right - left + 1) // 2\n",
    "\n",
    "                if ls[mid][1] >= st:\n",
    "                    right = mid - 1\n",
    "                else:\n",
    "                    left = mid\n",
    "            \n",
    "            if left == -1:\n",
    "                dp[i] = max(1, dp[i - 1])\n",
    "            else:\n",
    "                dp[i] = max(dp[i], 1 + dp[left], dp[i - 1])\n",
    "\n",
    "            max_ = max(max_, dp[i])\n",
    "\n",
    "        return max_\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonOverlapping(self, nums: List[int], target: int) -> int:\n",
    "        ls = []\n",
    "\n",
    "        sum_ = 0\n",
    "\n",
    "        mp = collections.defaultdict(int)\n",
    "        mp[0] = -1\n",
    "        for i, n in enumerate(nums):\n",
    "            sum_ += n \n",
    "            rem = sum_ - target\n",
    "\n",
    "            if rem in mp:\n",
    "                # ls.extend([[start + 1, i]for start in mp[rem]])\n",
    "                ls.append([mp[rem] + 1, i])\n",
    "            mp[sum_] = i\n",
    "\n",
    "        if len(ls) <= 1:\n",
    "            return len(ls)\n",
    "\n",
    "        \n",
    "        last_idx = [-1] * int(1e5 + 1)\n",
    "\n",
    "        for st, ed in ls:\n",
    "            last_idx[ed] = st\n",
    "        \n",
    "\n",
    "        dp = [0] * int(1e5 + 1)\n",
    "\n",
    "        if last_idx[0] != -1:\n",
    "            dp[0] = 1\n",
    "\n",
    "        max_ = dp[0]\n",
    "\n",
    "        for i in range(1, len(dp)):\n",
    "            dp[i] = dp[i - 1]\n",
    "\n",
    "            if last_idx[i] != -1:\n",
    "                dp[i] = max(dp[i], 1 + dp[last_idx[i] - 1]) \n",
    "\n",
    "            max_ = max(max_, dp[i])\n",
    "\n",
    "        return max_\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonOverlapping(self, nums: List[int], target: int) -> int:\n",
    "        # 不重叠区间的最大数量\n",
    "        # [l, r]\n",
    "        d = defaultdict(int)\n",
    "        d[0] = -1\n",
    "        preSum = 0\n",
    "        ret = []\n",
    "        for i, x in enumerate(nums):\n",
    "            preSum += x\n",
    "            if -target + preSum in d:\n",
    "                ret.append([d[-target + preSum] + 1, i])\n",
    "            d[preSum] = i\n",
    "        ret.sort()\n",
    "        # print(ret)\n",
    "        pre = -2\n",
    "        ans = 0\n",
    "        for l, r in ret:\n",
    "            if l > pre:\n",
    "                ans += 1\n",
    "                pre = r\n",
    "            else:\n",
    "                pre = min(r, pre)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonOverlapping(self, nums: List[int], target: int) -> int:\n",
    "        # 每个子数组的和都为target\n",
    "        # 非空不重叠子数组\n",
    "        # 子数组最大数目\n",
    "        # 前缀和可以快速求出子数组的和\n",
    "        prefix = [0]*(len(nums)+1)\n",
    "        for i in range(1,len(prefix)):\n",
    "            prefix[i] = prefix[i-1] + nums[i-1]\n",
    "        hashmap = {}\n",
    "        # 找出区间和为target的子数组\n",
    "        qujian = []\n",
    "        for i in range(len(prefix)):\n",
    "            if prefix[i]-target in hashmap:\n",
    "                qujian.append([hashmap[prefix[i]-target],i])\n",
    "            hashmap[prefix[i]] = i \n",
    "        # 转换成了0-1背包问题，哪些区间选，哪些区间不选，然后选择区间最多的方法\n",
    "        # print(qujian)\n",
    "        # if len(qujian) < 1:\n",
    "        #     return 0 \n",
    "\n",
    "        # 与0-1背包不同的点在于选择i区间的时候会影响前一个区间的选择\n",
    "        # 来一点贪心，这个就是课程表那类题型\n",
    "        \n",
    "        # 就直接贪心解决了，不用dp\n",
    "        # dp = [0]*len(qujian)\n",
    "        # dp[0] = 1\n",
    "        # res = 1\n",
    "        # for i in range(len(qujian)):\n",
    "        #     # 选i区间\n",
    "        #     st = qujian[i][0]\n",
    "        #     index = -1\n",
    "        #     for j in range(i-1,-1,-1):\n",
    "        #         if qujian[j][1] <= st:\n",
    "        #             index = j \n",
    "        #             break \n",
    "        #     if index == -1:\n",
    "        #         dp[i] = max(1,dp[i-1])\n",
    "        #     else:\n",
    "        #         dp[i] = max(1+dp[index],dp[i-1])\n",
    "        #     res = max(res,dp[i])\n",
    "        # return res\n",
    "\n",
    "        res = 0\n",
    "        end = 0  \n",
    "        for i in range(len(qujian)):\n",
    "            if qujian[i][0] >= end:\n",
    "                res += 1\n",
    "                end = qujian[i][1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonOverlapping(self, nums: List[int], target: int) -> int:\n",
    "        ls = []\n",
    "\n",
    "        sum_ = 0\n",
    "\n",
    "        mp = collections.defaultdict(int)\n",
    "        mp[0] = -1\n",
    "        for i, n in enumerate(nums):\n",
    "            sum_ += n \n",
    "            rem = sum_ - target\n",
    "\n",
    "            if rem in mp:\n",
    "                # ls.extend([[start + 1, i]for start in mp[rem]])\n",
    "                ls.append([mp[rem] + 1, i])\n",
    "            mp[sum_] = i\n",
    "\n",
    "        if len(ls) <= 1:\n",
    "            return len(ls)\n",
    "\n",
    "        \n",
    "        ls.sort(key = lambda x:x[1])\n",
    "\n",
    "        dp = [1] * len(ls)\n",
    "        \n",
    "\n",
    "        for i in range(1, len(dp)):\n",
    "            st, ed = ls[i]\n",
    "\n",
    "            # check ed < st 的最大值\n",
    "\n",
    "            left = -1\n",
    "            right = i - 1\n",
    "\n",
    "            while left < right:\n",
    "                mid = left + (right - left + 1) // 2\n",
    "\n",
    "                if ls[mid][1] >= st:\n",
    "                    right = mid - 1\n",
    "                else:\n",
    "                    left = mid\n",
    "            \n",
    "            if left == -1:\n",
    "                dp[i] = max(1, dp[i - 1])\n",
    "            else:\n",
    "                dp[i] = max(dp[i], 1 + dp[left], dp[i - 1])\n",
    "\n",
    "\n",
    "        return dp[-1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonOverlapping(self, nums: List[int], target: int) -> int:\n",
    "        ls = []\n",
    "\n",
    "        sum_ = 0\n",
    "\n",
    "        mp = collections.defaultdict(int)\n",
    "        mp[0] = -1\n",
    "        for i, n in enumerate(nums):\n",
    "            sum_ += n \n",
    "            rem = sum_ - target\n",
    "\n",
    "            if rem in mp:\n",
    "                # ls.extend([[start + 1, i]for start in mp[rem]])\n",
    "                ls.append([mp[rem] + 1, i])\n",
    "            mp[sum_] = i\n",
    "\n",
    "        if len(ls) <= 1:\n",
    "            return len(ls)\n",
    "\n",
    "        \n",
    "        last_idx = [-1] * int(1e5 + 1)\n",
    "\n",
    "        for st, ed in ls:\n",
    "            last_idx[ed] = st\n",
    "        \n",
    "\n",
    "        dp = [0] * int(1e5 + 1)\n",
    "\n",
    "        if last_idx[0] != -1:\n",
    "            dp[0] = 1\n",
    "\n",
    "        max_ = dp[0]\n",
    "\n",
    "        for i in range(1, len(dp)):\n",
    "            dp[i] = dp[i - 1]\n",
    "\n",
    "            if last_idx[i] != -1:\n",
    "                dp[i] = max(dp[i], 1 + dp[last_idx[i] - 1]) \n",
    "\n",
    "            max_ = max(max_, dp[i])\n",
    "\n",
    "        return max_\n",
    "\n",
    "        return max_\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonOverlapping(self, nums: List[int], target: int) -> int:\n",
    "        pre_sum = list(accumulate(nums, initial = 0))\n",
    "        n = len(pre_sum)\n",
    "        f = [0] * n\n",
    "        pos = defaultdict(int)\n",
    "        for i, x in enumerate(pre_sum):\n",
    "            f[i] = f[i - 1]\n",
    "            if x - target in pos:\n",
    "                p = pos[x - target]\n",
    "                f[i] = max(f[i], f[p] + 1)\n",
    "                #print(x, p, f)\n",
    "            pos[x] = i\n",
    "        return f[n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonOverlapping(self, nums: List[int], target: int) -> int:\n",
    "        d={0:-1}\n",
    "        p=0\n",
    "        n=len(nums)\n",
    "        a=[[] for _ in range(n)]\n",
    "        for i,x in enumerate(nums):\n",
    "            p+=x\n",
    "            if p-target in d:\n",
    "                a[i].append(d[p-target]+1)\n",
    "            d[p]=i\n",
    "        f=[0]*n\n",
    "        for i in range(n):\n",
    "            if i>0:\n",
    "                f[i]=f[i-1]\n",
    "            for j in a[i]:\n",
    "                if j==0:\n",
    "                    f[i]=max(f[i],1)\n",
    "                else:\n",
    "                    f[i]=max(f[i],f[j-1]+1)\n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonOverlapping(self, nums: List[int], target: int) -> int:\n",
    "        ans=0\n",
    "        n=len(nums)\n",
    "        dicc=defaultdict(list)\n",
    "        maxx=-1\n",
    "        summ=0\n",
    "        dicc[0].append(-1)\n",
    "        for i in range(n):\n",
    "            summ+=nums[i]\n",
    "\n",
    "            if summ-target in dicc and dicc[summ-target][-1]>=maxx:\n",
    "                ans+=1\n",
    "                maxx=i\n",
    "\n",
    "\n",
    "            dicc[summ].append(i)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonOverlapping(self, nums: List[int], target: int) -> int:\n",
    "        cnt, n = 0, len(nums)\n",
    "        def check(start):\n",
    "            nonlocal cnt\n",
    "            if start == n:\n",
    "                return\n",
    "            prefix = 0\n",
    "            preSet = set()\n",
    "            for i in range(start, n):\n",
    "                prefix += nums[i]\n",
    "                if prefix == target or prefix - target in preSet:\n",
    "                    cnt += 1\n",
    "                    break\n",
    "                preSet.add(prefix)\n",
    "            check(i+1)       \n",
    "\n",
    "        check(0)\n",
    "        return cnt"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
